package com.sheng.leetcode.year2023.month09.day13;

import org.junit.Test;

/**
 * @author by ls
 * @date 2023/9/13
 * <p>
 * 2596. 检查骑士巡视方案<p>
 * <p>
 * 骑士在一张 n x n 的棋盘上巡视。在有效的巡视方案中，骑士会从棋盘的 左上角 出发，并且访问棋盘上的每个格子 恰好一次 。<p>
 * 给你一个 n x n 的整数矩阵 grid ，由范围 [0, n * n - 1] 内的不同整数组成，<p>
 * 其中 grid[row][col] 表示单元格 (row, col) 是骑士访问的第 grid[row][col] 个单元格。骑士的行动是从下标 0 开始的。<p>
 * 如果 grid 表示了骑士的有效巡视方案，返回 true；否则返回 false。<p>
 * 注意，骑士行动时可以垂直移动两个格子且水平移动一个格子，或水平移动两个格子且垂直移动一个格子。<p>
 * 下图展示了骑士从某个格子出发可能的八种行动路线。<p>
 * <p>
 * 示例 1：<p>
 * 输入：grid = [[0,11,16,5,20],[17,4,19,10,15],[12,1,8,21,6],[3,18,23,14,9],[24,13,2,7,22]]<p>
 * 输出：true<p>
 * 解释：grid 如上图所示，可以证明这是一个有效的巡视方案。<p>
 * <p>
 * 示例 2：<p>
 * 输入：grid = [[0,3,6],[5,8,1],[2,7,4]]<p>
 * 输出：false<p>
 * 解释：grid 如上图所示，考虑到骑士第 7 次行动后的位置，第 8 次行动是无效的。<p>
 * <p>
 * 提示：<p>
 * n == grid.length == grid[i].length<p>
 * 3 <= n <= 7<p>
 * 0 <= grid[row][col] < n * n<p>
 * grid 中的所有整数 互不相同<p>
 */
public class LeetCode2596 {

    @Test
    public void test01() {
//        int[][] grid = {{0, 11, 16, 5, 20}, {17, 4, 19, 10, 15}, {12, 1, 8, 21, 6}, {3, 18, 23, 14, 9}, {24, 13, 2, 7, 22}};
        int[][] grid = {{0, 3, 6}, {5, 8, 1}, {2, 7, 4}};
        System.out.println(new Solution().checkValidGrid(grid));
    }
}

class Solution {

    int n;
    int[][] nums = {{2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}, {1, 2}};

    public boolean checkValidGrid(int[][] grid) {
        if (grid[0][0] != 0) {
            return false;
        }
        n = grid.length;
        return dfs(grid, 0, 0, 0);
    }

    public boolean dfs(int[][] grid, int index, int x, int y) {
        // 判断是否到达最后一个位置
        if (index == n * n - 1) {
            return true;
        }
        // 每条路径都进行行走一次
        for (int[] num : nums) {
            // 坐标不超出的情况下，下一个位置是否等于当前位置 + 1
            if (x + num[0] >= 0 && x + num[0] < n && y + num[1] >= 0 && y + num[1] < n && index + 1 == grid[x + num[0]][y + num[1]]) {
                return dfs(grid, index + 1, x + num[0], y + num[1]);
            }
        }
        return false;
    }
}
